package five;
import java.util.*;
public class A085 {

    //763.划分字母区间
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        char[] str = s.toCharArray();
        // Map<Character,Integer> hash = new HashMap<>(); //记录每个字母的下标
        //1.记录每个字符的最远右边界
        int[] hash = new int[26];
        for(int i=0;i<n;i++) {
            hash[str[i]-'a']=i;
        }
        //2.遍历--
        int start=0,end=0;
        List<Integer> ret = new ArrayList<>();
        for(int i=0;i<n;i++) {
            int cur = hash[str[i]-'a'];
            end = Math.max(end,cur); //该字符的最远右边界
            if(i == end) { //收集一次结果
                ret.add(end-start+1);
                start = end+1;
            }

        }
        return ret;
    }
}
